% 在本地编译时，采用XeLaTeX编译，pdfLaTeX可能编译失败

\documentclass[11pt]{article}

\usepackage[a4paper]{geometry}
\geometry{left=2.0cm,right=2.0cm,top=2.5cm,bottom=2.5cm}

\usepackage{ctex}
\usepackage{comment}
\usepackage{booktabs}
\usepackage{graphicx}
\usepackage{diagbox}
\usepackage{amsmath,amsfonts,graphicx,amssymb,bm,amsthm}
\usepackage{algorithm,algorithmicx}
\usepackage[noend]{algpseudocode}
\usepackage{fancyhdr}
\usepackage{tikz}
\usepackage{graphicx}
\usetikzlibrary{arrows,automata}
\usepackage{hyperref}

\setlength{\headheight}{14pt}

\newcounter{counter_exm}\setcounter{counter_exm}{1}
%\newcounter{counter_thm}\setcounter{counter_thm}{1}
%\newcounter{counter_lma}\setcounter{counter_lma}{1}
%\newcounter{counter_dft}\setcounter{counter_dft}{1}
%\newcounter{counter_clm}\setcounter{counter_clm}{1}
%\newcounter{counter_cly}\setcounter{counter_cly}{1}

\newtheorem{theorem}{\hskip 1.7em 定理}
\newtheorem{lemma}[theorem]{\hskip 1.7em 引理}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{\hskip 1.7em 命题}
\newtheorem{corollary}[theorem]{\hskip 1.7em 推论}
\newtheorem{definition}[theorem]{\hskip 1.7em 定义}

\renewcommand{\emph}[1]{\begin{kaishu}#1\end{kaishu}}

\newenvironment{solution}{{\noindent\hskip 2em \bf 解 \quad}}


\renewenvironment{proof}{{\noindent\hskip 2em \bf 证明 \quad}}{\hfill$\qed$\par}
\newenvironment{example}{{\noindent\hskip 2em \bf 例 \arabic{counter_exm}\quad}}{\addtocounter{counter_exm}{1}\par}

\newenvironment{concept}[1]{{\bf #1\quad} \begin{kaishu}} {\end{kaishu}\par}

\newcommand\E{\mathbb{E}}
\newcommand\N{\mathbb{N}}
\newcommand\Z{\mathbb{Z}}
\newcommand\R{\mathbb{R}}

% 以上是预定义宏等设置,在不熟悉LaTeX的情况下可不作修改.

% TODO: 在此处更改第X讲
\title{计算理论第1讲}
\usetikzlibrary{positioning}

\begin{document}

    \pagestyle{fancy}
    \lhead{\kaishu 北京大学}
    \chead{}
    \rhead{\kaishu 2020年春季学期计算理论导论}

    % TODO: 在此处更改第X讲、授课时间与记录人
    \begin{center}
        {\LARGE \bf 计算理论第1讲}\\
    \end{center}
        \begin{kaishu}
            授课时间: 2020年2月21日\quad
            授课教师: 孙晓明
            \hfill 记录人: 王宇萱、胡雨桐、陈嘉乐
        \end{kaishu}
    
    %%%%%%%%%%%%%%%%%%%%% Your note starts from here %%%%%%%%%%%%%%%%%%%%%

    \section{计算理论历史简介}
    1900年，在巴黎举行的第二届国际数学家大会上，希尔伯特做了一次堪称数学史上影响最为深远的演讲，题目是“数学问题”。在演讲中，希尔伯特列举了23个他认为最具重要意义的数学问题，这些问题被后人称为“希尔伯特问题”。其中第十个问题对所有丢番图方程即整系数多项式方程发起了挑战。问题的核心是“是否存在一个机械步骤，对任意一个不确定的丢番图方程，都能通过有限步的运算，即可以判定它是否存在整数解？”

    希尔伯特第十问题在当时留下了两个疑问。第一个疑问是科学的“算法”定义。在那个年代，有限的、机械的证明步骤在数学上还没有严格的定义，人们只能凭着感觉去定义这样一种模糊的表达方式。第二个疑问是问题的答案。如果问题的答案是否定的，那将意味着可能存在着大量数学问题人们永远无法知道其答案是否存在，自然也就无法去找到解决它的办法。人们面对这样的问题只能束手无策。因此一个可以计算的机器可能从诞生之初就有其无法逾越的极限。

    到了30年代，图灵和丘奇分别用图灵机和$\lambda$演算的方法，从不同的抽象角度提出了“有效机械算法“的概念。并且，他们在定义了什么是可计算、可判定后，用构造性的方法给出了一个不可判定的问题——停机问题，证明了图灵机具有理论的运算极限。1970年，苏联数学家马蒂塞维奇最终证明：在一般情况下，希尔伯特第十问题的答案是否定的。

    \section{P 与 NP}
    
    在证明了计算模型具有能力边界之后，人们转而关心该模型解决问题的效率。计算理论由算法和复杂性两部分组成：一方面，为了利用尽量少的资源解决问题，我们希望降低算法的复杂度；另一方面，通过复杂性分析，我们可以知道解决一个问题至少需要多少资源。一个问题的复杂性分析可以作为我们设计算法标杆，因而是十分重要的。而在现实中，我们一般认为能在多项式时间内被求解或者被验证的问题是可以被有效解决的，这就引出了P类与NP类。

    复杂度类P即为所有可以由一个确定型图灵机在多项式时间内解决的问题；复杂度类NP由所有可以由一个确定型图灵机在多项式时间内验证它的解是否正确的决定问题组成，或者等效的说，那些可以在非确定型图灵机上在多项式时间内找出解的问题的集合。由定义即可知道$\rm P\subseteq NP$，但两类问题是否相等仍是一个未解之谜。


    \subsection{归约}

        
    归约的直观理解，就是把做事情$A$归结为做事情$B$，再利用事情$B$回过头来帮助做事情$A$。那么，假如$A$可以归约到$B$，那么如果可以做$B$，则可以做$A$；如果不能做$A$，则不能做$B$。给出归约的方法之后，我们就可以比较两个问题之间的困难程度了。

    \subsection{NP-Hard 与 NP-Complete}
    我们最终想要解决的问题是回答P是否等于NP，而回答该问题的关键就在于我们找到NP类中最难的问题。假如这个问题不在类P中，那么显然$\rm P\neq NP$；否则，由于其最难的特点，我们可以得到$\rm P = NP$。

    而这里的所谓难易，就是由归约来判定。如果对于一个问题$A$，NP类中的所有问题都能归约到它，我们就称$A$是NP-Hard的。也就是说解决了$A$，我们就能解决所有NP问题。而如果$A$是NP-Hard的，同时它自身又属于NP类，我们就称$A$是NP-Complete问题。而NP-Complete问题就是NP类中最难的问题。判断NP-Complete问题是否属于P就是解决P与NP问题的关键。

    Stephen Cook 在 1971 年提出了上述的多项式归约想法与NP-Complete的想法，并且证明了3-SAT问题NP-Complete的。1972 年，Richard Karp 证明了有21个常见的问题可以互相归约而与3-SAT问题等价。
    
    比3-SAT问题难的问题被称作是NP-hard的，而NP-complete即NP-hard与NP的交集，即存在多项式方法验证的NP-hard问题。
\subsection{Karp遗留的问题}
    Karp遗留下了三个没有证明是NP-complete的问题，这些问题至今仍未能找到多项式时间验证的方法：
    
    \begin{itemize}
        \item 分解质因数(Factoring)
        \item 线性规划(Linear Programming)
        \item 图同构(Graph Isomorphism) 
    \end{itemize}
\subsubsection{分解质因数(Factoring)}
    分解质因数是否属于P还不知道，但是如果属于P会导致很大的问题，因为密码学很多应用是建立在“分解质因数是个难问题”的基础上。这是因为涉及到单向函数的概念，我们知道给两个大整数计算他们的乘积是很简单的，如果给定一个大整数对他进行因式分解很困难，我们可以通过这一点建立密码学应用。
    
    要注意的一点是因式分解问题与素数判定问题不一定是等价的，即可以不通过因式分解判定一个数是否为素数。事实上，素数判定问题在2002年Agrawal，Kayal和Saxena的论文Primes is in P中给出了一个多项式时间的确定性算法，主要想法涉及到
    \begin{lemma}
    	令$a\in\Z, n\in\N, n\geq 2$ 并且 $(a,n)=1$. 那么$n$为素数当且仅当$(X+a)^n=X^n+a\ (\text{mod } n)$。
    \end{lemma}
    \begin{lemma}
    	对$O(\log^kn)$的A，$\forall a\in[1,A],(X+a)^n=X^n+a\ (\text{mod } X^r - 1)(\text{mod } n)$当且仅当$n$为素数。
    \end{lemma}
    具体证明见算分论文。
    
\subsubsection{线性规划(Linear Programming)}
    Dantzig于1947年首次提出了单纯形法解决线性规划问题，这种算法在一般应用上运行的时间很短，但在某些例子上运行的复杂度是指数级别的。
    
    Khachian于1979年提出了椭球法，Karmarkar于1984年提出了内点法，这两个都是多项式时间解决单纯形问题的算法。
    
    Spielman,Teng在2001年指出对于单纯形需要运行指数级别时间的例子做一些扰动，单纯形法就可以在多项式时间运行。并且还定义了一种测度，在这个测度下单纯形法运行时间为指数级别的例子测度为0，可以说单纯形法在这个测度下测度1多项式时间运行。
    
\subsubsection{图同构(Graph Isomorphism)}
    图不同构问题属于IP问题，即可以设计出多项式时间的交互式证明算法，使验证者以高概率相信某个正确解的正确性。
    
    图同构问题也属于IP问题，并且可以证明图同构问题属于ZK问题（Zero-Knowledge），即存在一种交互式证明方法可以使验证者在验证过程中无法得到任何除了解是正确的以外的任何信息。
    
    2017年Babai给出了一个复杂度为$e^{\log^{O(1)}n}$的准多项式算法，但其正确性有待验证。

\subsection{密码学(Cryptography)}
    密码学是理论计算机很重要的一个方向。只有基于假设P $\neq$ NP时，才能建立真正的困难的问题，建立严格、安全的密码，构建密码学。基于假设factoring不在P里，即$n=pq$\ is\ HARD，Rivest,\ Shamir,\ Adleman在1979年提出了RSA密码（公钥密码），其算法基于$n$分解成$pq$是困难的，利用了欧拉的泛函数，本质上是把费马小定理推广到欧拉定理。
    \begin{itemize}
        \item $\Phi(n)=(p-1)(q-1),d·e\equiv1 \pmod {\phi(n)}$
        \item $E(M)=Me,D(C)=Cd \pmod n$
    \end{itemize}

    \begin{example}
        当二人远程石头剪刀布时，为了避免一方在得知另一方的结果时后再决定自己的结果，通过密码学，将其产生的结果加密之后发送给对方，使对方能够接受却无法破解，只有当另一方也产生结果时，另一方才能得知己方的结果。
    \end{example}
    
\subsection{电路模型(Circuit Complexity)}
    \begin{itemize}
        \item 任何一个P的问题，如果通过电路来解决，其电路复杂性也是多项式规模
        \item 每一个含有$n$个变量的问题，其都可以通过电路复杂性为$O(n2^n)$的电路来解决
        \item 香农在1949年指出，几乎所有含有$n$个变量的布尔函数$f$，其电路复杂性$C(f)\geq\frac{2^n}{n}$；Lupanov在1959年证明这个界是紧的，即任何$n$个变量的布尔函数都存在$\frac{(1+o(1))2^n}{n}$规模的电路
        \item Razborov在1985年证明，NP完全问题CLIQUE如果通过只有and和or的电路(Monotone电路)解决，其复杂度将超越多项式时间，$C(\text{CLIQUE})\geq n^{\Omega(\log n)}$
    \end{itemize}

\subsection{量子计算(Quantum Computing)}
    在量子计算模型下，factoring可以在多项式时间内解决，P. Shor在1994提出其可以在$O(n^3)$时间复杂度下算出(当前经典的算法时间复杂度为$2^{O(n^\frac{1}{3})}$)，而基于此条件RSA密码有可能不再安全。同时，在量子的计算模型下，Grover在1996年提出只需要$O(\sqrt{n})$的时间，就能判断一个元素是否在一个无序数组中，而不需要花$O(n)$的时间遍历整个数组。
    %%%%%%%%%%%%%%%%%%%%%%%%%%%% End %%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
\end{document}